package com.Oct_TwentyThree;

import java.util.HashMap;
import java.util.Map;

/**
 * 128. 最长连续序列
 * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
 *
 * 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-consecutive-sequence
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 *
 * 2022/10/23 16:02
 */

/**
 * 该题我使用了并查集的相关思想，由于数据过于庞大，无法使用数组来初始parent，所以我使用了map来进行操作，将num+1连到num上面
 * 然后使其成为连通分块，然后当寻找最长长度的时候，寻找每个连通分块的最右边界，再进行长度判断
 */

public class Solution128 {

    Map<Integer,Integer> map=new HashMap<>();


    void init(int[] nums){
        for (int num:nums){
            map.put(num,num);
        }
    }

    Integer find(int x){
        if (!map.containsKey(x)) return null;
        while (x!=map.get(x))
        {
            map.put(x,map.get(map.get(x)));
            x=map.get(x);
        }
        return x;
    }

    void union(int x,int y){
        x=find(x);
        y=find(y);
        if (x==y)
        {
            return;
        }
        map.put(x,y);
    }

    public int longestConsecutive(int[] nums) {
        init(nums);
        for (int num:nums){
            if (find(num+1)!=null)
            {
                union(num,num+1);
            }
        }
        int ans=0;
        for (int num:nums)
        {
            int right=find(num);
            ans=Math.max(ans,right-num+1);
        }
        return ans;
    }

    public static void main(String[] args) {
        Solution128 solution128=new Solution128();
        System.out.println(solution128.longestConsecutive(new int[]{0,3,7,2,5,8,4,6,0,1}));
    }
}
